#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    int minSteps(int n) {
        vector<int>ans(n + 1, 0);
        for(int i = 2; i <= n; i++){
            ans[i] = INT_MAX;
            for(int j = 1; j * j <= i; j++){
                if(!(i % j)){
                    ans[i] = min(ans[i], ans[j] + i / j);
                    ans[i] = min(ans[i], ans[i / j] + j);
                }   
            }
        }
        return ans[n];
    }
};

/**
 * 2021.9.19
 * 动态规划
 * dp[i] 为完成 i 个 'A' 的最小次数
 * 枚举 i 的所有因数 j, dp[i] = min(dp[i], dp[j] + i / j);
 * 有 i / j - 1 次粘贴和 1 次复制。
 */